﻿#include <iostream>
#include <string>
#include <math.h>

#define DEBUG

using std::cout;
using std::cin;
using std::string;

int Str_in_Str_serach_brute( string str, string sub_str ){
    int sub_i = 0;

    int strl = str.length();
    int sub_strl = sub_str.length();

    for( int i = 0; i < strl; ){
        if( sub_str[sub_i] == str[i] ){
            sub_i++;
            i++;
            if( sub_i == sub_strl ){
                return i - sub_i;
            }
        }else{
            sub_i = 0;
            i++;
        }
    }
    return -1;
}

int Str_in_Str_search_KMP( const string& str, const string& sub_str ){
    int shift_tbl[100000] , shift = 0, a = 0, m = 0;

    int strl = str.length();
    int sub_strl = sub_str.length();

    if( sub_strl >  strl) return -1;

    shift_tbl[0] = 0;
    for( int i = 1; i < sub_strl; i++ ){
        if( sub_str[a] == sub_str[i]){
             ++a;
             ++shift;
        }else{
             a = 0;
             shift = 0;
        }
        shift_tbl[i] = shift;
    }
#ifdef DEBUG
    for( int k = 0; k < sub_strl; k++ ){
        cout << shift_tbl[k] << std::endl;
    }
#endif


    for( int u = 0; u <= strl; ){
         if( sub_str[m] == str[u] ){
            ++u;
            ++m;
            if( m >= sub_strl ){
                return u - m;
            }
         }else{
            if( m > 0 ){
                u += m - shift_tbl[m - 1] - m;
                m = m - shift_tbl[m - 1] - m;
            }else{
                ++u;
                m = 0;
            }
         }
    }
    return -1;
}

int hash( string str, int i, int j ){
    int result = 0, b = 0;
    for ( ; i < j; i++ ){
        result += (int) str[i] * pow( 2, b );
        b++;
    }
    return result;
}

int Str_in_Str_search_RK( string str, string sub_str ){
    const long int h1 = hash( sub_str, 0, sub_str.length() );
    long int h2 = hash( str, 0, sub_str.length() );

    #ifdef DEBUG
        cout << "Starting h1 is : " << h1 << std::endl;
        cout << "Starting h2 is : " << h2 << std::endl;
    #endif

    const int strl = str.length();
    const int sub_strl = sub_str.length();
    const int length = strl - sub_strl + 1;

    for( int i = 0; i < length; i++ ){
        if( h1 == h2 ){
            #ifdef DEBUG
            cout << "h1 == h2" << std::endl;
            #endif
            int a = i;
            int al = a + sub_strl;
            int b = 0;
            for( ; a < al; a++ ){
                if( str[a] != sub_str[b] ){
                    #ifdef DEBUG
                    cout << "strings didn't match on a = " << a << std::endl;
                    #endif
                    a = -1;
                    break;
                }else{
                    b++;
                }
            }
            if( a != -1 ){ return i; }
        }
        h2 = ( h2 - (int) str[i] ) / 2 + ( (int) str[i + sub_strl] ) * pow( 2, sub_strl - 1 ) ;
        #ifdef DEBUG
            cout << " h2 on step " << i << " is : " << h2 << std::endl;
        #endif

    }
    return -1;
}

int main(){
    string str, sub_str;
    cin >> str;
    cin >> sub_str;
    cout << "Result:" << Str_in_Str_search_RK( str, sub_str );
    return 0;
}
